#include <bits/stdc++.h>
using namespace std;
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
using ll = long long;
void solve()
{
    ll n;
    cin >> n;
    string s;
    cin >> s;

    bool flag = false;
    for (ll i = 1; i < n; i++)
    {
        if (s[i] == s[i - 1])
            flag = true;
    }
    if (!flag)
        {
            cout << 0 << endl;
            return;
        }
    string a, b;
    for (ll i = 0; i < n; i++)
    {
        if (i % 2)
        {
            a += '1';
            b += '0';
        }
        else
        {
            a += '0';
            b += '1';
        }
    }
    ll ans1 = 0, ans2 = 0, ans = 0;
    string s1 = s, s2 = s;
    for (ll i = 0; i < n; i++)
    {
        if (s1[i] != a[i])
        {
            if (i + 1 != n)
            {
                ans1++;
                s1[i] = (s1[i] == '1' ? '0' : '1');
                s1[i + 1] = (s1[i + 1] == '1' ? '0' : '1');
            }
            else
            {
                ans1 = 1e9;
                break;
            }
        }
    }

    for (ll i = 0; i < n; i++)
    {
        if (s2[i] != b[i])
        {
            if (i + 1 != n)
            {
                ans2++;
                s2[i] = (s2[i] == '1' ? '0' : '1');
                s2[i + 1] = (s2[i + 1] == '1' ? '0' : '1');
            }
            else
            {
                ans2 = 1e9;
                break;
            }
        }
    }
    ans = min(ans1, ans2);
    if (ans >= 1e9)
        cout << -1 << endl;
    else
        cout << ans << endl;
}
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
